#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    // For all substrings till len/2 length check if we can form the main string

    bool isMatch(string &s, int startIndex, string sub)
    {
        // cout<<startIndex << " "<< sub<<endl;
        int subIndex = 0;
        for (int i = startIndex; i < s.size(); ++i)
        {
            if (subIndex == sub.size())
            {
                subIndex = 0;
            }
            if (s[i] != sub[subIndex])
            {
                return false;
            }
            subIndex++;
        }
        return true;
    }

    bool repeatedSubstringPattern(string s)
    {

        for (int size = 1; size <= s.size() / 2; ++size)
        {
            if (s.size() % size != 0)
            {
                continue;
            }
            // string subS = s.substr(0, size);
            if (isMatch(s, size, s.substr(0, size)))
            {
                return true;
            }
        }
        return false;
    }

    inline bool IsASubstringRepeatedkTimes(const string &s, int k)
    {
        int end = s.size() - k;
        for (int i = 0; i < end; ++i) // while s[i + k] is defined
            if (s[i] != s[i + k])
                return false;
        return true;
    }
    bool repeatedSubstringPattern_2(string s)
    {
        const int n = s.size();
        for (int k = n / 2; k > 0; --k)
            if (n % k == 0 && IsASubstringRepeatedkTimes(s, k))
                return true;
        return false;
    }

    bool repeatedSubstringPattern_3(string s)
    {
        // ababababab
        // ababcababc
        int i = 1;
        int j = 0;
        int n = s.size();
        if (n < 2)
        {
            return false;
        }
        vector<int> d(n + 1, 0);
        // d[i + 1] – наибольший суффикс до iго который ещё и префикс
        while (i < n)
        {
            if (s[i] == s[j])
            {
                d[++i] = ++j;
            }
            else
            {
                if (j == 0)
                {
                    ++i;
                }
                else
                {
                    j = d[j];
                }
            }
        }
        return d[n] && (d[n] % (n - d[n]) == 0);
    }
};
int main()
{
    /**
     * @brief
     * a 0
     * "ababba" 0
     *
     */
    Solution s;
    cout << s.repeatedSubstringPattern("abcabcabdcabc") << endl;
    return 0;
}
